/**
 * @Author ZhangCuirong
 * @Date 2025/9/12 10:54
 * @description:
 */
public class Main1 {
    //1-n个元素中查找缺失的一个数
    //一个1~n的自然数的乱序数组，其中缺失了1到n之间的某个数，如何快速找出这个数？
    // 使用异或法查找缺失的一个数
    public static int findMissingOne(int[] nums) {
        int n = nums.length + 1; // 原数组应有n个元素（1~n）
        int xorResult = 0;

        // 先将1~n的所有数进行异或
        for (int i = 1; i <= n; i++) {
            xorResult ^= i;
        }

        // 再与数组中的元素进行异或
        for (int num : nums) {
            xorResult ^= num;
        }

        // 最终结果就是缺失的数
        return xorResult;
    }

    public static void main(String[] args) {
        // 测试用例
        int[] test1 = {1, 2, 3, 5}; // 缺失4
        int[] test2 = {2, 3, 4, 5}; // 缺失1
        int[] test3 = {1, 2, 3, 4}; // 缺失5
        int[] test4 = {3}; // 缺失1（n=2）
        int[] test5 = {1, 3, 4, 5, 6}; // 缺失2

        System.out.println(findMissingOne(test1)); // 输出：4
        System.out.println(findMissingOne(test2)); // 输出：1
        System.out.println(findMissingOne(test3)); // 输出：5
        System.out.println(findMissingOne(test4)); // 输出：1
        System.out.println(findMissingOne(test5)); // 输出：2
    }
}
